/*
 * 百度在线网络技术（北京）有限公司拥有本软件版权2022并保留所有权利。
 * Copyright 2022, Baidu.com,Inc 2:Baidu Online Network Technology (Beijing) Co.,Ltd,
 * All rights reserved.
 */

package com.azdebugit.suanfa.test.teshuawei.test.快慢指针;

/**
 * Title：NC-3，链表的入口节点，环的入口节点
 * Description：双指针
 *
 * @author WZQ
 * @version 1.0.0
 * @date 2021/3/5
 */
public class NC3 {

    /**
     * 1）首先判断是否有环,有环时，返回相遇的节点，无环，返回null
     * 2）有环的情况下， 求链表的入环节点
     * fast再次从头出发，每次走一步，
     * slow从相遇点出发，每次走一步，
     * 再次相遇即为环入口点。
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }

        ListNode meetNode = meetingNode(head);
        //说明无环
        if (meetNode == null) {
            return null;
        }

        //fast再次从头出发，每次走一步，
        //slow从相遇点出发，每次走一步，
        ListNode fast = head;
        ListNode slow = meetNode;
        //再次相遇即为环入口点
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow;
    }

    //寻找相遇节点，如果无环，返回null
    public ListNode meetingNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            // 快指针走2步
            slow = slow.next;
            fast = fast.next.next;
            // 相遇点
            if (slow == fast) {
                return slow;
            }
        }
        return null;
    }

    //节点
    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

}
